Many different classes of digital video data compression techniques are used to compress digital video data. Block compression techniques are a class of techniques which compress digital video data on a block-by-block basis. A block (also known as a "cell") refers to a fixed-size group of pixels. A cell is typically formed by a two-dimensional symmetric group of pixels, such as two pixels by two pixels, four pixels by four pixels or sixteen pixels by sixteen pixels. Block compression techniques seek to compress the non-compressed color data that is provided for each of the pixels of a cell. The non-compressed color data of a pixel typically encodes red component information, green component information and blue component information for the pixel.
FIG. 1 shows a flowchart of the steps performed by one conventional block compression technique. In this technique, each frame of image data is divided into cells of four pixels by four pixels. The cells are compressed by an iterative procedure until all of the cells in the image have been compressed. In accordance with this iterative procedure, before compressing each cell in the image, the technique checks whether compression is complete for the frame by determining if any cells remain to be compressed (step 10). If no cells remain to be compressed, the compression of the frame is complete. In contrast, if there are still cells left to be compressed, the color data for the next cell is obtained (step 12), and the color data for the cell is compressed (step 14).
FIG. 2 is a flowchart showing the steps performed by the block compression technique of FIG. 1 in compressing a cell of the image (see step 14 in FIG. 1). Initially, the luminance for each pixel in the cell is calculated (step 16). Once the luminance for all of the pixels in the cells have been calculated, the minimum luminance (min) and the maximum luminance (max) among the pixels of the cell are determined (step 18). The difference between the maximum luminance and the minimum luminance is then compared with a fixed, non-adjustable threshold value (step 20). The difference between the maximum luminance and the minimum luminance specifies the variance in the luminances of the pixels. This value of the variance is used to determine what compression approach to employ. If the variance is not greater than the threshold, the steps shown in the flowchart of FIG. 3 are performed. However, if the variance is greater than the threshold, the steps shown in the flowchart of FIG. 5 are performed.
The steps shown in the flowchart of FIG. 3 will now be described. The average luminance of the pixels in the cell is calculated (step 22). A check is made to determine whether any pixels are left to be examined in the cell (step 24). If an unexamined pixel remains, the pixel is examined by obtaining the luminance of the pixel (step 26) and comparing the luminance of the pixel with the average luminance of the cell (step 28). If the luminance of the pixel is not greater than the average luminance, the pixel is marked as being in the set of dimmer pixels (step 30). On the other hand, if the luminance of the pixel is greater than the average luminance, the pixel is marked as being in the set of brighter pixels (step 32). Steps 24, 26, 28, and 30 or 32 are then repeated for the remaining pixels in the cell. When all of the pixels have been examined, the steps shown in the flowchart of FIG. 4 are performed.
In accordance with the steps shown in FIG. 4, the average color for the set of brighter pixels is calculated (step 34). The average color is then assigned as the color of each of the pixels in the set of brighter pixels (step 36). The assignment of the average color to the pixels in the set of brighter pixels is realized by manipulating a bit mask for the cell (see 48 in FIG. 6a and 54 in FIG. 6b), as will be described below. The average color for the set of dimmer pixels is, likewise, calculated (step 38). The average color for the set of dimmer pixels is then assigned as the color of each of the pixels in the set of dimmer pixels (step 40). As a result, each four-pixels-by-four-pixels cell has two colors assigned to its pixels.
The assignment of colors to the pixels in the compressed color data is realized by appropriately setting the corresponding bits in a bit mask representing the cell. The bit mask includes a bit at a specified position in the bit mask. The bit specifies the color of the pixel as one of the two possible color choices. The average color of the set of brighter pixels is associated with one of the possible bit values (i e., "1" or "0"), and the average color of the set of dimmer pixels is associated with the other possible bit value. Hence, each bit value in the bit mask specifies the color of the associated pixel as either the average color of the set of brighter pixels or the average color of the set of dimmer pixels.
The above discussion has focused on the instances in which the variance is less than the threshold value, as checked by step 20 of FIG. 2. If, however, the variance is greater than the threshold, the steps shown in FIG. 5 are performed. In particular, the cell of four pixels by four pixels is divided into four sub-cells of two pixels by two pixels (step 42). The block compression technique of FIG. 1 then applies the compression approach of FIG. 3 iteratively for each of the two-by-two sub-cells. Each sub-cell is treated as if it is a separate cell. In order to iteratively apply this approach, a check is made to determine whether any two-by-two sub-cells are left to be examined (step 44). The non-compressed color data for the next sub-cell of two pixels by two pixels is obtained (step 46), and the above-described steps of the flowchart of FIG. 3 are performed. The main difference between the application of these steps with the sub-cells and the application of these steps with the four-pixels-by-four-pixels cells is the difference in the size of the cells to which the steps are applied. In particular, each sub-cell is two pixels by two pixels, whereas each cell is four pixels by four pixels. Steps 44 and 46 and the steps of FIG. 3 are repeated for each of the remaining sub-cells until all four of the sub-cells have been compressed.
The compressed color data resulting from the above-described compression technique is shown in FIGS. 6a and 6b. FIG. 6a shows the resulting compressed color data for the first described approach, wherein each cell of four pixels by four pixels is compressed without further division into sub-cells. The compressed color data includes a sixteen-bit bit mask 48 holding a bit for each pixel at a specified position in the bit mask. Each bit specifies the color of each pixel in the cell as being one of two choices: the average color of the set of brighter pixels or the average color of the set of dimmer pixels. In particular, a "1" value for a bit in the bit mask specifies a first color of the two possible colors for the pixels, and a "0" value for the bit specifies the other possible color. The color information for the set of brighter pixels is stored in a data word 50. The data word 50 includes five bits dedicated to red component information, five bits dedicated to green component information and five bits dedicated to blue component information. The leading bit of the data word 50 has a value of "0". An analogous data word 52 is produced for encoding the average color of the set of dimmer pixels.
FIG. 6b shows the compressed color data, wherein the original cell is divided into four two-pixels-by-two-pixels sub-cells. The compressed color data includes a sixteen-bit bit mask 54 that designates the colors of the respective pixels in the cell. The assignment of pixels to sub-cells is fixed and, thus, which sub-cell a pixel belongs to is known. Accordingly, the two color choices for each pixel are known, and the color for any pixel may be designated by a single bit in the bit mask 54. The bit mask 54 designates these choices by including a "0" or "1" in the bit position for the associated pixel. The compressed color information also includes, for each of the sub-cells, a data word encoding the average color of the set of brighter pixels and a data word encoding the average color of the set of dimmer pixels. Thus, data words 56 and 58 encode the color information for sub-cell #0. Similarly, data words 60 and 62 encode the color information for sub-cell #1; data words 64 and 66 encode the color information for sub-cell #2; and data words 68 and 70 encode the sub-cell information for cell #3. The leading bit of word 56, however, has a value of "1" rather than a value of "0" for the two-color case, so that it is known that the color information following the bit mask is for two-by-two sub-cells rather than a four-by-four cell.